{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d09a5c42",
   "metadata": {},
   "source": [
    "Copyright © 2023 Gurobi Optimization, LLC"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b522f9d",
   "metadata": {},
   "source": [
    "# Airline planning after flight disruption"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ed2a0ed",
   "metadata": {},
   "source": [
    "Weather events are a major threat to the airline industry. The unpredictable nature of snowstorms, heavy rains, and icy runways make it difficult for aviation planners to make accurate schedules. \n",
    "These events can lead to flight delays and cancellations, causing not only inconvenience for passengers but also significant financial losses for airlines. \n",
    "The 2014 winter polar vortex, for instance, is estimated to have cost the industry and passengers a staggering $1.4 billion in losses due to disrupted flights [(CNBC, 2014)](https://www.cnbc.com/2014/01/08/weather-flight-disruptions-cost-14-billion-data.html). \n",
    "Thus, managing weather-related issues and having contingency plans in place is critical for the success of any airline business."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e91ff2a8",
   "metadata": {},
   "source": [
    "\n",
    "<!--  <img height=\"227.4774774774775px\" src=\"https://media3.giphy.com/media/gkAEM5sXCFqB465YWg/giphy.gif?cid=de9bf95e87544fzo1lm01e68i3mxxou95x5zgiewz66hwi45&amp;rid=giphy.gif&amp;ct=g\" width=\"700px\" itemtype=\"http://schema.skype.com/Giphy\" key=\"gif_0\"> -->\n",
    " \n",
    " |<img src=\"https://raw.githubusercontent.com/Gurobi/modeling-examples/master/aviation_planning/image_snowstorm.jpeg\" width=\"500\" align=\"center\">| \n",
    "|:--:|\n",
    "| <b>Flight cancellations due to weather delays are more common than we think. Image Credits: [Travel Refund](https://travelrefund.com/articles/when-do-flights-get-cancelled-due-to-weather/) </b>| "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09401da0",
   "metadata": {},
   "source": [
    "Suppose that you are a flight planner for an airline. For a given day, you have sold tickets for flights across the country, and you have a plan for operating your aircraft fleet to service all of these flights. \n",
    "\n",
    "Let us say that on this day, there is a weather event (such as a snowstorm) that inhibits the airports from operating at full capacity. This means that some flights have to get cancelled. When a flight will be cancelled, the aircrafts assigned to these flights have to be re-routed. So the question becomes: how can airlines decide which flights to operate/cancel and how to best re-route the aircrafts? \n",
    "\n",
    "There is no straight-forward answer to this question, but mathematical optimization can help.\n",
    "\n",
    "\n",
    "This notebook walks through the optimization problem of deciding which flights to operate and which flights to cancel after a weather disruption.\n",
    "We do this by constructing a **mathematical optimization** model that reduces the revenue lost from the cancelled flights.\n",
    "In this example, we are using real data in France compiled by [Amadeus](https://amadeus.com/en).\n",
    "\n",
    "There are three parts to this notebook.\n",
    "- First, we read the datasets.\n",
    "- Second, we build the optimization model by defining the **decision variables**, **objective function**, and the **constraints**.\n",
    "- Third, assuming a certain level of weather disruption, we solve the optimization model to find the new optimal flight plan as well as routes for the aircrafts."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b5f497e",
   "metadata": {},
   "source": [
    "## The data\n",
    "\n",
    "\n",
    "**Dataset**: We use real data compiled by [Amadeus](https://amadeus.com/en), made available as part of the [ROADEF 2009 Challenge: Disruption Management for Commercial Aviation](https://www.roadef.org/challenge/2009/en/). This dataset is based on flight plans for an airline in France. For this notebook, we have pre-processed this dataset and stored the information in three parts:\n",
    "\n",
    "- **Current flight plan:** The currently planned set of flights and their aircraft assignments assuming that there is no weather disruption (i.e., all airports operate at full capacity).\n",
    "- **Aircraft starting and ending positions:** Where should each aircraft start the day and end the day? This information is necessary to ensure that aircrafts are where they need to be for the next day so that the disruption does not extend into the next day.\n",
    "- **Passenger itinerary:** The number of passengers and the price per ticket sold for each flight. This information is useful to assess the revenue brought in by each flight.\n",
    "\n",
    "Note that even though the data used in this example is from 2006, the optimization model is ambivalent of the data.\n",
    "For any new flight plan and predicted future disruption levels, the model will optimally solve the routing and flight service decisions.\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76bb1f3d",
   "metadata": {},
   "source": [
    "### Packages\n",
    "First, install and import the Python packages needed for processing the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "8e7ebe49",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install networkx matplotlib seaborn\n",
    "import pandas as pd    \n",
    "import matplotlib.pyplot as plt  \n",
    "import seaborn as sns  \n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "from datetime import datetime, timedelta\n",
    "import random\n",
    "import csv\n",
    "import plotly.express as px"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ff2fcd2",
   "metadata": {},
   "source": [
    "### Flight plan without disruption\n",
    "\n",
    "Next, read the  planned schedule of flights on the day of disruption, i.e., 7th January, 2006. Additionally, we infer the origin and destination airports for each flight, as well as the start time (when the flight departs the origin airport) and the end time (when the flight arrives at the destination airport).\n",
    "We store it in a Pandas dataframe.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "e7ec8dcd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>flight</th>\n",
       "      <th>date</th>\n",
       "      <th>aircraft</th>\n",
       "      <th>ori</th>\n",
       "      <th>des</th>\n",
       "      <th>start_time</th>\n",
       "      <th>end_time</th>\n",
       "      <th>duration</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#1</td>\n",
       "      <td>CDG</td>\n",
       "      <td>ORY</td>\n",
       "      <td>00:00:00</td>\n",
       "      <td>00:30:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>73</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#3</td>\n",
       "      <td>ORY</td>\n",
       "      <td>CDG</td>\n",
       "      <td>00:00:00</td>\n",
       "      <td>00:30:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#2</td>\n",
       "      <td>CDG</td>\n",
       "      <td>ORY</td>\n",
       "      <td>00:20:00</td>\n",
       "      <td>00:50:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>74</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#4</td>\n",
       "      <td>ORY</td>\n",
       "      <td>CDG</td>\n",
       "      <td>00:20:00</td>\n",
       "      <td>00:50:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>75</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#1</td>\n",
       "      <td>ORY</td>\n",
       "      <td>CDG</td>\n",
       "      <td>00:40:00</td>\n",
       "      <td>01:10:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>603</th>\n",
       "      <td>142</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#4</td>\n",
       "      <td>ORY</td>\n",
       "      <td>CDG</td>\n",
       "      <td>23:00:00</td>\n",
       "      <td>23:30:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>604</th>\n",
       "      <td>143</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#1</td>\n",
       "      <td>ORY</td>\n",
       "      <td>CDG</td>\n",
       "      <td>23:20:00</td>\n",
       "      <td>23:50:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>605</th>\n",
       "      <td>71</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#3</td>\n",
       "      <td>CDG</td>\n",
       "      <td>ORY</td>\n",
       "      <td>23:20:00</td>\n",
       "      <td>23:50:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>606</th>\n",
       "      <td>144</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#2</td>\n",
       "      <td>ORY</td>\n",
       "      <td>CDG</td>\n",
       "      <td>23:40:00</td>\n",
       "      <td>00:10:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>607</th>\n",
       "      <td>72</td>\n",
       "      <td>7/1/06</td>\n",
       "      <td>TranspCom#4</td>\n",
       "      <td>CDG</td>\n",
       "      <td>ORY</td>\n",
       "      <td>23:40:00</td>\n",
       "      <td>00:10:00</td>\n",
       "      <td>00:30:00</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>608 rows × 8 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     flight    date     aircraft  ori  des start_time  end_time  duration\n",
       "0         1  7/1/06  TranspCom#1  CDG  ORY   00:00:00  00:30:00  00:30:00\n",
       "1        73  7/1/06  TranspCom#3  ORY  CDG   00:00:00  00:30:00  00:30:00\n",
       "2         2  7/1/06  TranspCom#2  CDG  ORY   00:20:00  00:50:00  00:30:00\n",
       "3        74  7/1/06  TranspCom#4  ORY  CDG   00:20:00  00:50:00  00:30:00\n",
       "4        75  7/1/06  TranspCom#1  ORY  CDG   00:40:00  01:10:00  00:30:00\n",
       "..      ...     ...          ...  ...  ...        ...       ...       ...\n",
       "603     142  7/1/06  TranspCom#4  ORY  CDG   23:00:00  23:30:00  00:30:00\n",
       "604     143  7/1/06  TranspCom#1  ORY  CDG   23:20:00  23:50:00  00:30:00\n",
       "605      71  7/1/06  TranspCom#3  CDG  ORY   23:20:00  23:50:00  00:30:00\n",
       "606     144  7/1/06  TranspCom#2  ORY  CDG   23:40:00  00:10:00  00:30:00\n",
       "607      72  7/1/06  TranspCom#4  CDG  ORY   23:40:00  00:10:00  00:30:00\n",
       "\n",
       "[608 rows x 8 columns]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_current_plan = pd.read_csv('https://raw.githubusercontent.com/Gurobi/modeling-examples/master/aviation_planning/data/flight_rotations_2006-07-01.csv') \n",
    "# if you run this notebook locally, you can also use\n",
    "#df_current_plan = pd.read_csv('data/flight_rotations_2006-07-01.csv') \n",
    "\n",
    "df_current_plan['start_time'] = pd.to_datetime(df_current_plan['start_time'], format='%H:%M')\n",
    "df_current_plan['start_time'] = df_current_plan['start_time'].dt.time\n",
    "df_current_plan['end_time'] = pd.to_datetime(df_current_plan['end_time'], format='%H:%M')\n",
    "df_current_plan['end_time'] = df_current_plan['end_time'].dt.time\n",
    "df_current_plan['duration'] = pd.to_datetime(df_current_plan['duration'], format='%H:%M')\n",
    "df_current_plan['duration'] = df_current_plan['duration'].dt.time\n",
    "df_current_plan"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38c5f401",
   "metadata": {},
   "source": [
    "How many **flights**, **airports** and **aircrafts** are in this dataset?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "e2c5ae06",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "608 flights between 35 airports operated with 85 aircrafts\n"
     ]
    }
   ],
   "source": [
    "flights = df_current_plan['flight'].unique()\n",
    "aircrafts = df_current_plan['aircraft'].unique()\n",
    "airports = set(df_current_plan['ori'].unique()+df_current_plan['des'].unique())\n",
    "\n",
    "print(len(flights),\"flights between\",len(airports),\"airports operated with\",len(aircrafts),\"aircrafts\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3202c799",
   "metadata": {},
   "source": [
    "### Visualizing the flight network\n",
    "\n",
    "Next, we assemble the origin-destination airports for all the flights, and visualize the entire network of planned flights. We use networkx to store the inter-airport information as a *directed graph* data structure to enable this visualization.\n",
    "\n",
    "\n",
    "Moreover, to reduce the size of the inputs, we can select just the top few airports (in terms of how many flights flow through them) for the rest of the notebook. The n_airports parameter selects the number of top airports to pre-select, with default set to 20 airports.\n",
    "\n",
    "\n",
    "The visual below is intended to illustrate the complexity of the flight map; do not feel like you need to spend too much time analyzing it. We will drill down into specific flight paths later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "e336df26",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The reduced data has 222 flights between 4 airports operated with 21 aircrafts\n"
     ]
    }
   ],
   "source": [
    "from IPython.display import Image, display\n",
    "import networkx as nx\n",
    "from networkx.drawing.nx_agraph import graphviz_layout\n",
    "from networkx.drawing.nx_agraph import to_agraph \n",
    " \n",
    "arcs = list(df_current_plan[['ori','des']].itertuples(index=False, name=None)) # store the origin-destination pairs of all the flights\n",
    "\n",
    "n_airports = 4 # specify how many airports to pick\n",
    "    \n",
    "G = nx.MultiDiGraph() # create an empty directed graph\n",
    "G.add_edges_from(arcs) # add the origin-destination pairs to the graph as directed edges\n",
    "\n",
    "top_airports = [i for (i,j) in sorted(G.degree, key=lambda x: x[1], reverse=True)[:n_airports]] # pre-select top airports by their degree\n",
    "\n",
    "G = G.subgraph(top_airports) # reduce the graph to just the top few airports\n",
    " \n",
    "# reduce the current plan dataframe to just the top few airports    \n",
    "df_current_plan = df_current_plan[df_current_plan['ori'].isin(top_airports)] \n",
    "df_current_plan = df_current_plan[df_current_plan['des'].isin(top_airports)]\n",
    "\n",
    "# # visualize the network\n",
    "# A_graph = to_agraph(G) \n",
    "# A_graph.layout('dot')    \n",
    "# display(A_graph) \n",
    " \n",
    "\n",
    "flights = df_current_plan['flight'].unique()\n",
    "aircrafts = df_current_plan['aircraft'].unique()\n",
    "airports = set(df_current_plan['ori'].unique()+df_current_plan['des'].unique())\n",
    "\n",
    "print(\"The reduced data has\",len(flights),\"flights between\",len(airports),\"airports operated with\",len(aircrafts),\"aircrafts\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c29757d",
   "metadata": {},
   "source": [
    "For each flight, we will store its origin airport, destination airport, starting time and ending time in dictionaries.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "446c28f6",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "\n",
    "flight_origin = df_current_plan.set_index('flight')['ori'].to_dict()\n",
    "flight_dest = df_current_plan.set_index('flight')['des'].to_dict()\n",
    "flight_start_time = df_current_plan.set_index('flight')['start_time'].to_dict()\n",
    "flight_end_time = df_current_plan.set_index('flight')['end_time'].to_dict() \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c47345d1",
   "metadata": {},
   "source": [
    "### Where should aircrafts start the day and end the day?\n",
    "\n",
    "At the start of the disruption day, each aircraft starts from a particular airport, and must end the day at a particular airport. This is to ensure that the aircraft fleet is ready and available for uninterrupted flight operations for the next day.\n",
    "\n",
    "We now read the information on the aircraft fleet's starting position (called the **source**) and ending position (called the **sink**). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "b55bad82",
   "metadata": {},
   "outputs": [],
   "source": [
    "df_starting_positions = pd.read_csv('https://raw.githubusercontent.com/Gurobi/modeling-examples/master/aviation_planning/data/starting_positions.csv')  \n",
    "# if you run this notebook locally, you can also use\n",
    "#df_starting_positions = pd.read_csv('data/starting_positions.csv')  \n",
    "aircrafts_startpositions_airc = df_starting_positions.set_index('aircraft')['airport'].to_dict()\n",
    "\n",
    "df_ending_positions = pd.read_csv('https://raw.githubusercontent.com/Gurobi/modeling-examples/master/aviation_planning/data/ending_positions.csv')\n",
    "# if you run this notebook locally, you can also use\n",
    "#df_ending_positions = pd.read_csv('data/ending_positions.csv')\n",
    "aircrafts_endpositions_airc = df_ending_positions.set_index('aircraft')['airport'].to_dict()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1c64419",
   "metadata": {},
   "source": [
    "### Passenger itineraries\n",
    "\n",
    "Next, we read the passenger itinerary data. For each flight, we know how many passengers booked the tickets and the cost of each seat. We will store this information in dictionaries so that we can later assess the cost of cancelling a flight."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "8e921413",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>cost</th>\n",
       "      <th>n_pass</th>\n",
       "      <th>flight</th>\n",
       "      <th>total_cost</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>137.5</td>\n",
       "      <td>24.0</td>\n",
       "      <td>4296.0</td>\n",
       "      <td>3300.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>137.5</td>\n",
       "      <td>33.0</td>\n",
       "      <td>4296.0</td>\n",
       "      <td>4537.5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>137.5</td>\n",
       "      <td>24.0</td>\n",
       "      <td>4296.0</td>\n",
       "      <td>3300.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>137.5</td>\n",
       "      <td>44.0</td>\n",
       "      <td>4296.0</td>\n",
       "      <td>6050.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>137.5</td>\n",
       "      <td>35.0</td>\n",
       "      <td>4295.0</td>\n",
       "      <td>4812.5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1925</th>\n",
       "      <td>200.0</td>\n",
       "      <td>15.0</td>\n",
       "      <td>2620.0</td>\n",
       "      <td>3000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1926</th>\n",
       "      <td>250.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>2609.0</td>\n",
       "      <td>1500.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1927</th>\n",
       "      <td>250.0</td>\n",
       "      <td>4.0</td>\n",
       "      <td>2609.0</td>\n",
       "      <td>1000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1928</th>\n",
       "      <td>325.0</td>\n",
       "      <td>16.0</td>\n",
       "      <td>5125.0</td>\n",
       "      <td>5200.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1929</th>\n",
       "      <td>325.0</td>\n",
       "      <td>11.0</td>\n",
       "      <td>5125.0</td>\n",
       "      <td>3575.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>1930 rows × 4 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "       cost  n_pass  flight  total_cost\n",
       "0     137.5    24.0  4296.0      3300.0\n",
       "1     137.5    33.0  4296.0      4537.5\n",
       "2     137.5    24.0  4296.0      3300.0\n",
       "3     137.5    44.0  4296.0      6050.0\n",
       "4     137.5    35.0  4295.0      4812.5\n",
       "...     ...     ...     ...         ...\n",
       "1925  200.0    15.0  2620.0      3000.0\n",
       "1926  250.0     6.0  2609.0      1500.0\n",
       "1927  250.0     4.0  2609.0      1000.0\n",
       "1928  325.0    16.0  5125.0      5200.0\n",
       "1929  325.0    11.0  5125.0      3575.0\n",
       "\n",
       "[1930 rows x 4 columns]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_iterinaries = pd.read_csv('https://raw.githubusercontent.com/Gurobi/modeling-examples/master/aviation_planning/data/flight_iterinaries.csv')\n",
    "#df_iterinaries = pd.read_csv('data/flight_iterinaries.csv')\n",
    "df_iterinaries['total_cost'] = df_iterinaries['cost']*df_iterinaries['n_pass']\n",
    "flight_revenue = df_iterinaries.groupby(['flight'])['total_cost'].agg('sum').to_dict() \n",
    "flight_n_pass = df_iterinaries.groupby(['flight'])['n_pass'].agg('sum').to_dict() \n",
    "df_iterinaries\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bcc1480",
   "metadata": {},
   "source": [
    "### Create flight-to-flight transitions for each aircraft\n",
    "\n",
    "Finally, using the current flight plan, we assess all the feasible flight-to-flight transitions. Such a transition is  essentially: after each flight, what is the next possible flight?\n",
    "\n",
    "For two flights $f_1$ and $f_2$, the flight transition $f_1$-$f_2$ is *feasible* if the arrival time of $f_1$ is before the departure time of $f_2$, and the destination of $f_1$ is the same as the origin of $f_2$.\n",
    "\n",
    "Based on these feasible transitions, each aircraft's route is a sequence of flight-to-flight transitions starting from the source airport to its sink airport.\n",
    "\n",
    "\n",
    "For example, from the data, the aircraft A380#1 (which is an Airbus 380) starts the day at airport CFE. From here, it can either take flight 4296 (CFE-ORY) at 5:40am or flight 4298 (CFE-ORY) at 10:48am. Once it gets to ORY, it will have multiple options for the rest of the day's route. In total,  A380#1 has eight flight paths (see visualization below).\n",
    "\n",
    "To compactly store all the feasible flight-to-flight transitions, we create a **directed acyclic graph** (DAG). The vertices are the flights, and the directed edges are feasible transitions. Use the interactive tool below to visualize the DAG for each aircraft."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "0e8cd389",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "\n",
    "from ipywidgets import interact, interactive, fixed, interact_manual\n",
    "\n",
    "aircraft_flights = df_current_plan.groupby(['aircraft']).apply(lambda x: x['flight'].tolist()).to_dict()\n",
    "flight_arcs_for_each_aircraft = {}\n",
    "deltaplus_flightarcs = {}\n",
    "deltaminus_flightarcs = {}\n",
    "for a in aircraft_flights:\n",
    "    aircraft_flights[a] += ['source_%s'%a,'sink_%s'%a]\n",
    "    flight_origin['source_%s'%a] = aircrafts_endpositions_airc[a]\n",
    "    flight_dest['source_%s'%a] = aircrafts_startpositions_airc[a]\n",
    "    flight_origin['sink_%s'%a] = aircrafts_endpositions_airc[a]\n",
    "    flight_dest['sink_%s'%a] = aircrafts_startpositions_airc[a]\n",
    "\n",
    "    flight_start_time['source_%s'%a] = datetime.strptime('0:0', '%H:%M').time()\n",
    "    flight_end_time['source_%s'%a] = datetime.strptime('0:0', '%H:%M').time()\n",
    "\n",
    "    flight_start_time['sink_%s'%a] = datetime.strptime('23:59', '%H:%M').time()\n",
    "    flight_end_time['sink_%s'%a] = datetime.strptime('23:59', '%H:%M').time()\n",
    "\n",
    "    flight_arcs_for_each_aircraft[a] = []\n",
    "    deltaplus_flightarcs[a] = {f: [] for f in aircraft_flights[a]}\n",
    "    deltaminus_flightarcs[a] = {f: [] for f in aircraft_flights[a]}\n",
    "\n",
    "    for f1 in aircraft_flights[a]:\n",
    "        for f2 in aircraft_flights[a]:\n",
    "            if f1!=f2 and flight_end_time[f1] < flight_start_time[f2] and flight_dest[f1] == flight_origin[f2]: \n",
    "                flight_arcs_for_each_aircraft[a].append((f1,f2))\n",
    "                deltaplus_flightarcs[a][f1].append(f2)\n",
    "                deltaminus_flightarcs[a][f2].append(f1) \n",
    "            # allow to connect source and target directly for the case that aircraft is not used at all    \n",
    "            elif str(f1).startswith('source') and str(f2).startswith('sink'):\n",
    "                flight_arcs_for_each_aircraft[a].append((f1,f2))\n",
    "                deltaplus_flightarcs[a][f1].append(f2)\n",
    "                deltaminus_flightarcs[a][f2].append(f1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d5fecea",
   "metadata": {},
   "outputs": [],
   "source": [
    "# packages needed to visualize the DAG\n",
    "# uncomment the whole cell in case of troubles\n",
    "!apt install libgraphviz-dev\n",
    "!pip install pygraphviz \n",
    "\n",
    "def visualize_aircraft_network(x): \n",
    "    G = nx.DiGraph()\n",
    "    G.add_edges_from(flight_arcs_for_each_aircraft[x])\n",
    "    plt.figure(figsize=(20,14)) \n",
    "    A_graph = to_agraph(G) \n",
    "    A_graph.layout('dot')    \n",
    "    display(A_graph)             \n",
    "    plt.show()\n",
    " \n",
    "interact(visualize_aircraft_network, x=aircraft_flights.keys())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f83a44db",
   "metadata": {},
   "source": [
    "## Optimization model"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36b3b9d9",
   "metadata": {},
   "source": [
    " \n",
    "A weather disruption diminishes the overall capacity of the airports, measured by the number of flights that can take-off and land.\n",
    "Given this reduced airport capacity, which flights should be operated, and what route should the aircrafts take?\n",
    "Our goal is to create an optimal flight plan that minimizes the overall revenue loss incurred from the cancelled flights.\n",
    "\n",
    "This decision problem is modeled using a mathematical optimization model, which finds the **best solution** according to an **objective function** such that the solution satisfies a set of **constraints**. \n",
    "Here, a solution is expressed as a vector of real values or integer values called **decision variables**.\n",
    "Constraints are a set of equations or inequalities written as a function of the decision variables.\n",
    "\n",
    "In this airline business model, the objective is to minimize the overall loss from all the cancelled flights.\n",
    "The decision variables decide which flights to operate/cancel, as well as construct a route for each aircraft that starts from its starting airport and ends at the airport it needs to be at the end of the day.\n",
    "There are three types of constraints: (i) construct the flight route, (ii) ensure that a flight is operated only if it is in the flight route, and (iii) ensure that the number of take-offs and landings are within the diminished capacity of the airports."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48080a9f",
   "metadata": {},
   "source": [
    "### Assumptions\n",
    "\n",
    "There are many modeling assumptions made in this notebook, as this model serves as a starting point. At the end of the notebook, we suggest potential extensions.\n",
    "The following are some key assumptions.\n",
    "- All airports have the same level of disruption, which is across the entire day.\n",
    "- We assume that we know ahead of time the level of disruption at all airports.\n",
    "- We ignore crew scheduling and maintainance issues; though this model can be extended for larger inputs with a commercial Gurobi licence.\n",
    "- We do not consider how other airlines may react to the disruption.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e5c6469",
   "metadata": {},
   "source": [
    "\n",
    "### Input Parameters\n",
    "\n",
    "Let us now define the input parameters and notations used for creating the model. The subscript $a$ will be used to denote each aircraft, $f$ for each flight, and $i$ for each airport.\n",
    "\n",
    "\n",
    "- $N$: set of all airports\n",
    "- $A$: set of all aircrafts\n",
    "- $F$: set of all flights\n",
    "- $F_a$: set of flights operated by aircraft $a$ in the current plan\n",
    "- $E_a$: set of feasible flight-to-flight transitions for aircraft $a$ \n",
    "- $r_f$: revenue ($\\$$) from operating flight $f$\n",
    "- $(o_f,d_f)$: origin, destination airports for flight $f$\n",
    "- $(C^{arr}_i,C^{dep}_i)$: maximum number of arrivals and departures in airport $i$\n",
    "- $\\alpha$: level of disruption\n",
    "\n",
    "The following code loads the Gurobi python package and initiates the optimization model. \n",
    "The value of $\\alpha$ is set to $50\\%$. \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "32e94cb9",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "model = gp.Model(\"airline_disruption\")\n",
    " \n",
    "N = G.nodes() "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b6aca52",
   "metadata": {},
   "source": [
    "### Decision Variables\n",
    "\n",
    "We now define the decision variables.\n",
    "In our model, we want to do two things: pick flights to be operated by each aircraft and construct a route for each aircraft. \n",
    "The following notation is used to model these decision variables.\n",
    "\n",
    "\n",
    "$x_{a,f}$: $1$, if aircraft $a$ operates flight $f$; $0$, otherwise\n",
    "\n",
    "$y_{a,f_1,f_2}$: $1$, if aircraft $a$ operates flight $f_2$ immediately after flight $f_1$; $0$, otherwise\n",
    "\n",
    "We will now add the variables to the Gurobi model using the addVar function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "83f94e78",
   "metadata": {},
   "outputs": [],
   "source": [
    "x, y = {}, {}\n",
    "for a in aircrafts:\n",
    "    for f in aircraft_flights[a]:\n",
    "        x[a,f] = model.addVar(name=\"x_%s,%s\"%(a,f), vtype=GRB.BINARY)\n",
    "\n",
    "    for (f1,f2) in flight_arcs_for_each_aircraft[a]:\n",
    "        y[a,f1,f2] = model.addVar(name=\"y_%s,%s,%s\"%(a,f1,f2), vtype=GRB.BINARY)\n",
    "\n",
    "model.update()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b3b2c0c",
   "metadata": {},
   "source": [
    "\n",
    "### Set the Objective: minimize the revenue from cancelled flights\n",
    "\n",
    "<!-- Next, we will define the objective function: we want to maximizing the **net revenue**. The revenue from sales in each region is calculated by the price of an avocado in that region multiplied by the quantity sold there. There are two types of costs incurred: the wastage costs for excess unsold avocados and the cost of transporting the avocados to the different regions. \n",
    "\n",
    "The net revenue is the sales revenue subtracted by the total costs incurred. We assume that the purchase costs are fixed and are not incorporated in this model. -->\n",
    "\n",
    "Our goal is to **minimize** the total **lost revenue** from the cancelled flights. \n",
    "We capture this objective as a function of the decision variables.\n",
    "Note that a flight is cancelled if $x_{a,f}$ is set to $0$.\n",
    "The revenue lost from the flight is given by $(1-x_{a,f}) * r_f$.\n",
    "Hence, the overall lost revenue across all aircrafts and cancelled flights is given by,\n",
    "\n",
    "\n",
    "<!-- \\begin{aligned} \n",
    "\\textrm{Maximize } \\ \\sum_{f \\in flights} \\ \\sum_{a \\in aircrafts} \\ x_{a,f} * r_f\n",
    "\\end{aligned} -->\n",
    "\n",
    "\\begin{aligned} \n",
    "\\textrm{Minimize } \\ \\sum_{a \\in aircrafts} \\ \\sum_{f \\in F_a} \\ (1-x_{a,f}) * r_f\n",
    "\\end{aligned}\n",
    "\n",
    "We now add this objective function to the model using the setObjective function.\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "8938547c",
   "metadata": {},
   "outputs": [],
   "source": [
    "objective = gp.quicksum((1-x[a,f])*flight_revenue[f] for a in aircrafts for f in aircraft_flights[a] if f in flight_revenue) # operating cost\n",
    "model.setObjective(objective, sense=GRB.MINIMIZE)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4580444",
   "metadata": {},
   "source": [
    "### Constraint #1: construct each aircraft's flight path\n",
    "\n",
    "\n",
    "An aircraft begins the day from its starting airport (source) and ends the day at its final airport (sink). Its route during the day is constructed using the **y** decision variables. \n",
    "\n",
    "We do this by considering three cases for each aircraft: its starting flight, an intermediary flight, and its ending flight.\n",
    "\n",
    "When a flight leaves its starting airport, we ensure that it can leave exactly once.\n",
    "The flights in the set $\\delta^+(source_a)$ gives the set of all candidate \"first-flights\" for the aircraft.\n",
    "We ensure that exactly one of these flights is taken using the following equality for each aircraft $a$.\n",
    "\n",
    "\\begin{aligned} \n",
    "\\sum_{f' \\in \\delta^+(source_a)} y_{a,source_a,f'} &= 1\n",
    "\\end{aligned} \n",
    "\n",
    "Similarly, a flight arrives at its final airport, we ensure that it enters the airport exactly once.\n",
    "The flights in the set $\\delta^-(sink_a)$ gives the set of all candidate \"last-flights\" for the aircraft, and we ensure that exactly one of these flights is taken.\n",
    "\n",
    "\\begin{aligned} \n",
    "\\sum_{f' \\in \\delta^-(sink_a)} y_{a,f',sink_a} &= 1\n",
    "\\end{aligned}\n",
    "\n",
    "For every intermediary flight $f$ in $F_a$ (that is neither the starting nor the ending flight), we ensure that the number of preceding and succeeding flights are the same. This is necessary to ensure the continuity of the flight path.\n",
    "The following constraints are for each aircraft $a$ and  intermediary flight $f$ in $F_a$.\n",
    "\n",
    "\\begin{aligned} \n",
    "\\sum_{f' \\in \\delta^+(f)} y_{a,f,f'} &= \\sum_{f' \\in \\delta^-(i)} y_{a,f',f} \n",
    "\\end{aligned}\n",
    "\n",
    "In optimization modeling, these types of constraints are called **flow-balance** constraints.\n",
    "These are used to model many famous problems such as shortest path, maximum flow problem, and the traveling salesman problem. Read more [here](https://web.mit.edu/15.053/www/AMP-Chapter-08.pdf).\n",
    "The following code adds these constraints to the model one at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "7fe10530",
   "metadata": {},
   "outputs": [],
   "source": [
    "for a in aircrafts:\n",
    "    model.addConstr(sum(y[a,'source_%s'%a,f2] for f2 in deltaplus_flightarcs[a]['source_%s'%a]) == 1)\n",
    "    model.addConstr(sum(y[a,f1,'sink_%s'%a] for f1 in deltaminus_flightarcs[a]['sink_%s'%a]) == 1)\n",
    "    for f in aircraft_flights[a]: \n",
    "        if str(f)[0] != 's':\n",
    "            model.addConstr(sum(y[a,f,f2] for f2 in deltaplus_flightarcs[a][f]) == sum(y[a,f1,f] for f1 in deltaminus_flightarcs[a][f]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94ab229f",
   "metadata": {},
   "source": [
    "### Constraint #2: a flight is operated only if it is traversed by an aircraft\n",
    "\n",
    "Next, we make sure that a flight $f$ is operated by an aircraft $a$ only if $f$ is in the route taken by $a$.\n",
    "The quantity $\\sum_{f' \\in \\delta^+(f)} y_{a,f,f'}$ gives us the number of arcs that leave flight $f$; there can be either $0$ arcs or $1$ arc. \n",
    "If this quantity is $0$, then aircraft $f$ does not traverse flight $f$, and we set $x_{a,f}$ to be $0$.\n",
    "This constraint can be mathematically expressed by the following inequality for each aircraft $a$ and flight $f$ in $F_a$\n",
    "\n",
    "\\begin{aligned}  \n",
    "x_{a,f} &\\leq \\sum_{f'\\ \\textrm{in }\\ \\delta^+(f)} y_{a,f,f'}\n",
    "\\end{aligned}\n",
    "\n",
    "Let us now add these constraints to the model.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "ba744ca1",
   "metadata": {},
   "outputs": [],
   "source": [
    "for a in aircrafts:\n",
    "    for f in aircraft_flights[a]:\n",
    "        model.addConstr(x[a,f] <= sum(y[a,f,f2] for f2 in deltaplus_flightarcs[a][f])) # flight f is chosen only if it is traversed\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e404f868",
   "metadata": {},
   "source": [
    "### Constraint #3: maximum limit on the number of arrivals and departures from the airports \n",
    "\n",
    "Finally, we add the airport capacity constraints. \n",
    "For each airport, we know the total number of arrivals and departures on a regular day. \n",
    "However, on the disruption day, only a fraction of flights can land and take-off, given by the parameters $\\alpha$.\n",
    "For example, if $\\alpha = 0.5$, only half the flights can land or take-off.\n",
    "This condition can be mathematically expressed using the following inequalities for every airport $i$,\n",
    "\n",
    "\\begin{aligned} \n",
    "\\sum_{\\textrm{aircraft a}} \\ \\sum_{\\textrm{flight }f \\textrm{ that arrives at $i$}} x_{a,f} &\\leq C^{arr}_{i} * \\alpha \\quad  \\forall \\ \\textrm{airport } i, \\\\\n",
    "\\sum_{\\textrm{aircraft a}} \\ \\sum_{\\textrm{flight }f \\textrm{ that departs from $i$}} x_{a,f} &\\leq C^{dep}_{i} *\\alpha \\quad  \\forall \\ \\textrm{airport } i.\n",
    "\\end{aligned}\n",
    "\n",
    "The left hand side of the inequalities counts the total number of flights that land or take-off at the airports, and the right hand side sets the maximum limits.\n",
    "As extreme cases, setting $\\alpha  = 0$ implies that there is a complete shut-down of the airports, and $\\alpha = 1$ implies that there is no disruption.\n",
    "\n",
    "We can add these constraints to the model, with a default values set to $0.5$. Later in the notebook, we see how the disruption parameter affects the optimal flight plan.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "600c2bbd",
   "metadata": {},
   "outputs": [],
   "source": [
    "alpha = .5 \n",
    "\n",
    "for i in N:\n",
    "    total_departures = len([f for a in aircrafts for f in aircraft_flights[a] if flight_origin[f] == i])\n",
    "    total_arrivals = len([f for a in aircrafts for f in aircraft_flights[a] if flight_dest[f] == i])\n",
    "\n",
    "    model.addConstr(sum(x[a,f] for a in aircrafts for f in aircraft_flights[a] if flight_origin[f] == i) <= alpha*total_departures)\n",
    "    model.addConstr(sum(x[a,f] for a in aircrafts for f in aircraft_flights[a] if flight_dest[f] == i) <= alpha*total_arrivals)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dc03a5f",
   "metadata": {},
   "source": [
    "### Fire up Gurobi engines\n",
    "\n",
    "We have added the decision variables, objective function, and the constraints to the model. \n",
    "The model is ready to be solved. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "8e1742c1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)\n",
      "\n",
      "CPU model: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 536 rows, 1920 columns and 5742 nonzeros\n",
      "Model fingerprint: 0x8cf95899\n",
      "Variable types: 0 continuous, 1920 integer (1920 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [6e+03, 6e+04]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 6e+01]\n",
      "Found heuristic solution: objective 1878476.0000\n",
      "Presolve removed 498 rows and 1559 columns\n",
      "Presolve time: 0.03s\n",
      "Presolved: 38 rows, 361 columns, 722 nonzeros\n",
      "Found heuristic solution: objective 801512.00000\n",
      "Variable types: 0 continuous, 361 integer (344 binary)\n",
      "\n",
      "Explored 0 nodes (0 simplex iterations) in 0.04 seconds (0.01 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 2: 801512 1.87848e+06 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 8.015120000000e+05, best bound 8.015120000000e+05, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "model.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "671c663d",
   "metadata": {},
   "source": [
    "### Optimal solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f000f511",
   "metadata": {},
   "source": [
    "The solver solved the optimization problem in less than a second.\n",
    "Let us now analyze the optimal solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "3a31a92d",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Net revenue total loss: $ 0.8 million\n",
      "Optimal number of flights served: 50\n",
      "Optimal number of passengers transported: 5641.0\n",
      "Optimal number of aircrafts utilized: 10\n"
     ]
    }
   ],
   "source": [
    "operated_flights = {a: [f for f in aircraft_flights[a] if x[a,f].X > .5 if str(f)[0] != 's'] for a in aircrafts}\n",
    "\n",
    "print(\"\\nNet revenue total loss: $\",round(model.objVal/10**6,2),'million')\n",
    "print(\"Optimal number of flights served:\",sum(len(operated_flights[a]) for a in aircrafts))\n",
    "print(\"Optimal number of passengers transported:\",sum(sum(flight_n_pass[f] for f in aircraft_flights[a] if x[a,f].X > .5) for a in aircrafts))\n",
    "print(\"Optimal number of aircrafts utilized:\",sum([1 if len(operated_flights[a]) > 0 else 0 for a in aircrafts]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d70590d",
   "metadata": {},
   "source": [
    "## Full model\n",
    "\n",
    "While this notebook walked through how to build an optimization model piece-by-piece, the following code contains the overall optimization model. You can input different parameter values and see how the optimal solution changes. \n",
    "The value of $\\alpha$ (percentage disruption) can be controlled using the slider below the cell.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "706f85d8",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Select a value for the level of disruption at the airports:\n",
      "\n",
      "Select 0 for complete shutdown of all airports; select 1 for business-as-usual.\n",
      "\n"
     ]
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "f6257ef1e05e4158b3b13ef56a0b3341",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(FloatSlider(value=0.0, description='x', max=1.0, step=0.05), Output()), _dom_classes=('w…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "<function __main__.solve_flight_planning(x)>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "from ipywidgets import interact, interactive, fixed, interact_manual, widgets\n",
    " \n",
    "N = G.nodes() \n",
    " \n",
    "def solve_flight_planning(x):    \n",
    "    alpha = x \n",
    "    \n",
    "    model = gp.Model(\"airline_disruption\")\n",
    "    x, y = {}, {}\n",
    "    for a in aircrafts:\n",
    "        for f in aircraft_flights[a]:\n",
    "            x[a,f] = model.addVar(name=\"x_%s,%s\"%(a,f), vtype=GRB.BINARY)\n",
    "\n",
    "        for (f1,f2) in flight_arcs_for_each_aircraft[a]:\n",
    "            y[a,f1,f2] = model.addVar(name=\"y_%s,%s,%s\"%(a,f1,f2), vtype=GRB.BINARY)\n",
    "\n",
    "    model.update()\n",
    "\n",
    "    objective = gp.quicksum((1-x[a,f])*flight_revenue[f] for a in aircrafts for f in aircraft_flights[a] if f in flight_revenue) # operating cost\n",
    "    model.setObjective(objective, sense=GRB.MINIMIZE)\n",
    "\n",
    "    for a in aircrafts:\n",
    "        model.addConstr(sum(y[a,'source_%s'%a,f2] for f2 in deltaplus_flightarcs[a]['source_%s'%a]) == 1)\n",
    "        model.addConstr(sum(y[a,f1,'sink_%s'%a] for f1 in deltaminus_flightarcs[a]['sink_%s'%a]) == 1)\n",
    "        for f in aircraft_flights[a]: \n",
    "            if str(f)[0] != 's':\n",
    "                model.addConstr(sum(y[a,f,f2] for f2 in deltaplus_flightarcs[a][f]) == sum(y[a,f1,f] for f1 in deltaminus_flightarcs[a][f]))\n",
    "\n",
    "    for a in aircrafts:\n",
    "        for f in aircraft_flights[a]:\n",
    "            model.addConstr(x[a,f] <= sum(y[a,f,f2] for f2 in deltaplus_flightarcs[a][f])) # flight f is chosen only if it is traversed\n",
    "\n",
    "\n",
    "    for i in N:\n",
    "        total_departures = len([f for a in aircrafts for f in aircraft_flights[a] if flight_origin[f] == i])\n",
    "        total_arrivals = len([f for a in aircrafts for f in aircraft_flights[a] if flight_dest[f] == i]) \n",
    "\n",
    "        model.addConstr(sum(x[a,f] for a in aircrafts for f in aircraft_flights[a] if flight_origin[f] == i) <= alpha*total_departures)\n",
    "        model.addConstr(sum(x[a,f] for a in aircrafts for f in aircraft_flights[a] if flight_dest[f] == i) <= alpha*total_arrivals)\n",
    "\n",
    "    model.setParam('OutputFlag', 0)\n",
    "    model.optimize()\n",
    "\n",
    "    operated_flights = {a: [f for f in aircraft_flights[a] if x[a,f].X > .5 if str(f)[0] != 's'] for a in aircrafts}\n",
    "    actual_rev = sum(flight_revenue[f] for f in flight_revenue) # operating cost\n",
    "    print(\"Loss ($): \",round(model.objVal/10**6,2),'million')\n",
    "    print(\"Optimal number of flights served:\",sum(len(operated_flights[a]) for a in aircrafts))\n",
    "    print(\"Optimal number of passengers transported:\",sum(sum(flight_n_pass[f] for f in aircraft_flights[a] if x[a,f].X > .5) for a in aircrafts))\n",
    "    print(\"Optimal number of aircrafts utilized:\",sum([1 if len(operated_flights[a]) > 0 else 0 for a in aircrafts]))\n",
    "    \n",
    "    # the following lines are for visualization and needs the package pygraphviz (can be commented in case of troubles)\n",
    "    print(\"Full network of operated flights:\")\n",
    "    G = nx.MultiDiGraph()\n",
    "    arcs=[(flight_origin[f],flight_dest[f]) for a in aircrafts for f in operated_flights[a]] \n",
    "     \n",
    "    aircraft_color = {aircrafts[i]:\"#\"+''.join([random.choice('0123456789ABCDEF') for j in range(6)]) for i in range(len(aircrafts))}\n",
    "    for a in aircrafts:\n",
    "        for f in operated_flights[a]:\n",
    "            G.add_edge(flight_origin[f],flight_dest[f],color=aircraft_color[a])\n",
    "    A_graph = to_agraph(G) \n",
    "    A_graph.layout('dot')  \n",
    "    display(A_graph)\n",
    "\n",
    "print(\"Select a value for the level of disruption at the airports:\\n\")\n",
    "print(\"Select 0 for complete shutdown of all airports; select 1 for business-as-usual.\\n\")\n",
    "\n",
    "interact(solve_flight_planning, x=(0,1,0.05)) \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "9f338b8f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Freeing default Gurobi environment\n"
     ]
    }
   ],
   "source": [
    "model.dispose()\n",
    "gp.disposeDefaultEnv()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d132b2c",
   "metadata": {},
   "source": [
    "## Extensions\n",
    "\n",
    "- Besides cancelling flights, there are other ways to alter the schedule after a disruption, such as delaying a flight, rebooking the passengers onto other flights, etc. Can you model these using decision variables? What type of constraints are needed?\n",
    "- We only consider the cost of cancelling a flight. There may be other costs due to maintainance and repair, that we don't consider. How can other costs be incorporated into the model?\n",
    "- There are indirect considerations to crew planning that this model does not include. For example, when reserve crew misses a connection due to a flight cancellation, that crew won't be able to serve a future flight. Can crew planning be captured in the model as well? \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "066b5fd3",
   "metadata": {},
   "source": [
    "Copyright © 2023 Gurobi Optimization, LLC"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
